package com.base.dfs;

public class FloodFill {
    /**
     * 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
     *
     * 给你一个坐标(sr, sc)表示图像渲染开始的像素值（行 ，列）和一个新的颜色值newColor，让你重新上色这幅图像。
     *
     * 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，
     * 重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
     * 最后返回经过上色渲染后的图像
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/flood-fill
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    //标注2 通过两个矩阵表示一个点前后左右的四个点
    int[] xx = {0, 0, 1, -1};
    int[] yy = {1, -1, 0, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {

        int curColor = image[sr][sc];
        // 只有当前结点
        if (curColor != newColor) {
            dfs(image, sr, sc, curColor, newColor);
        }
        return image;
    }

    public void dfs(int[][] image, int x, int y, int color, int newColor) {
        //标注1
        //出口：判断当前点的颜色，是否为需要更新的颜色
        if (image[x][y] == color) {
            image[x][y] = newColor;
            // 代表着4个维度上面的更新
            for (int i = 0; i < 4; i++) {
                // 标注，遍历四周的点
                int mx = x + xx[i];
                int my = y + yy[i];
                // image[x1][y1] == color  这里无需判断颜色
                if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
                    dfs(image, mx, my, color, newColor);
                }
            }
        }
    }

    public static void main(String[] args) {
        FloodFill floodFill = new FloodFill();
        int[][] image={{1,1,1},{1,1,0},{1,0,1}};
        floodFill.floodFill(image,1,1,2);

    }
}
